package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.ListNode;

/**
 * 对链表进行插入排序
 * https://leetcode.cn/problems/insertion-sort-list/
 *
 * @time 2024/1/19
 */
public class InsertionSortList {

//    public static void main(String[] args) {
//        InsertionSortList isl = new InsertionSortList();
////        -1, 5, 3, 4, 0
//        ListNode l_1 = new ListNode(-1);
//        ListNode l0 = new ListNode(0);
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(2);
//        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(5);
//
////        l_1.next = l5;
////        l5.next = l3;
////        l3.next = l4;
////        l4.next = l0;
//
//        l4.next = l2;
//        l2.next = l1;
//        l1.next = l3;
//
//        isl.insertionSortList(l4);
//    }

    public ListNode insertionSortList(ListNode head) {
        ListNode first = new ListNode();
        first.next = head;
        ListNode tmp = head, inlast = first, outLast = first;
        while (tmp != null) {
            ListNode node = tmp, min = tmp, minLast = null;
            while (null != node) {
                if (node.val <= min.val) {
                    minLast = inlast;
                    min = node;
                }
                inlast = node;
                node = node.next;
            }
            if (min != tmp) {
                minLast.next = min.next;
                min.next = outLast.next;
                outLast.next = min;
            }
            outLast = min;
            inlast = min;
            tmp = outLast.next;
        }
        return first.next;
    }
}
